package leetcode.D200.T101;

import util.TreeNode;

class Solution {
    /* 迭代解法
        public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        Deque<TreeNode> leftdq = new LinkedList<>();
        Deque<TreeNode> rightdq = new LinkedList<>();
        leftdq.addLast(root.left);
        rightdq.addLast(root.right);
        while(!leftdq.isEmpty() && !leftdq.isEmpty()) {
            TreeNode leftFront = leftdq.removeFirst();
            TreeNode rightFront = rightdq.removeFirst();
            if(leftFront != null && rightFront != null) {
                if(leftFront.val != rightFront.val) return false;
                leftdq.addLast(leftFront.left);
                leftdq.addLast(leftFront.right);
                rightdq.addLast(rightFront.right);
                rightdq.addLast(rightFront.left);
            } else if((leftFront != null && rightFront == null) || (leftFront == null && rightFront != null)) {
                return false;
            }
        }
        if(leftdq.isEmpty() && rightdq.isEmpty()) return true;
        else return false;
    }*/

    // 递归解法
    /*public boolean isSymmetric(TreeNode root) {
        return root == null ? true : isMirror(root.left, root.right);
    }
    private boolean isMirror(TreeNode leftRoot, TreeNode rightRoot) {
        if(leftRoot == null && rightRoot == null) return true;
        if(leftRoot != null && rightRoot != null) {
            if(leftRoot.val != rightRoot.val) return false;
            return isMirror(leftRoot.left, rightRoot.right) && isMirror(leftRoot.right, rightRoot.left);
        } else return false;
    }*/

    // 二刷
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return true;
        if (left != null && right != null) {
            if (left.val != right.val)
                return false;
            return isMirror(left.left, right.right) && isMirror(left.right, right.left);
        }
        return false;
    }
}